73C - LionAge II - CodeForces Solution

#include <bits/stdc++.h>

#define ll long long

#define pb push_back
#define el '\n'
#define pi 3.1415926536
#define mod 1000000007


#include <sstream>

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<typename T>
using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


ll const N = 1e5+5;

map<int, int> freqq;
map<pair<ll, ll>, ll> mpp;
map<int,int>mps,mp2;
vector<pair<int,int>>adj[N];
deque<pair<int,int>>pq2;
pair<int,int>p[N];


//priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<>>pq;

int dx[] = { 1, -1,0, 0 };
int dy[] = { 0,0, -1,1  };
int disx[]={0,0,-1};
int disy[]={1,-1,0};
int chess_x[] = { -1,-1,1,1, 1, -1, 0, 0 ,0};
int chess_y[] = { 1, -1,1,-1, 0,0, 1,-1,0 };
//ll a[80][80];


bool isPowerOfTwo(int x){
    return !(x & (x - 1));
}

ll mul(ll x, ll y)
{
    return ((x%mod) * (y%mod)) % mod;
}
ll add(ll x, ll y)
{
    return ((x%mod) + (y%mod)) % mod;
}
ll sub(ll x, ll y)
{
    return ((x%mod) - (y%mod)) % mod;
}
ll fastPow(ll b, ll p)
{
    if(p==0) return 1;

    ll hp = fastPow(b, p/2);
    ll ret = mul(hp, hp);

    if(p%2)
        ret = mul(ret, b);

    return ret;
}
ll modInverse(ll x)
{
    return fastPow(x, mod-2);
}

ll getbit(ll num,ll idx){
    return num&(1LL<<idx);
}

ll optimize_nCr(ll x,ll y) //  5C3 ->(x-0)/1 *(x-1)/2 *(x-2)/3
{
    ll m = 1;
    for (int i = 0; i < y; i++) {
        m = m * (x - i) / (i + 1);
    }
    return m;
}
string s;
int k,n;
int c[700],dp[120][120][30],a[28][28];
char x,y;
int solve(int indx,int mx,char c){
    if(mx<0)return -1e9;
    if(indx==s.size())return 0;
    int &ret=dp[indx][mx][c-'a'];
    if(~ret)return ret;
    ret=solve(indx+1,mx,s[indx])+a[c-'a'][s[indx] -'a'];
    for(char i='a';i<='z';i++){
        if(s[indx]!=i){
            ret=max(ret,solve(indx+1,mx-1,i)+a[c-'a'][i -'a']);
        }
    }
    return ret;
}

int main()
{
    fast;
    cin>>s>>k;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y>>c[i];
        a[x-'a'][y-'a'] = c[i];
    }
    ::memset(dp,-1,sizeof dp);
    cout<<solve(0,k,'{');

    return 0;
}